//这里面代码注释大部分在笔记里
//只记载实现

//栈和队列相关
//有效的括号
class Solution {
public:
    bool isValid(string s) {
        //遍历原字符串 遇见左括号进栈 遇见右括号出栈栈顶左括号相比
        stack<char> st;
        auto it =s.begin();
        while(it != s.end())
        {
            if(((*it) == '(') || ((*it) == '{') ||( (*it) == '['))
            {
                //进栈
                st.push(*it);
                it++;
            }
            else
            {
                //遇见右括号了  取栈顶比较
                //如果刚开始遇见右括号 栈是空的 不能取栈顶
                if(st.empty())
                {
                    return false;
                }
                char top = st.top();
                st.pop();
                if((top == '(' && *it == ')')
                 || (top == '{' && *it == '}')
                  || (top == '['&& *it == ']'))
                {
                    it++;
                }
                else{
                    //不匹配
                    return false;
                }
            }
        }

        return st.empty();
    }
};

//用队列实现栈
class MyStack {
public:
    MyStack() {}
    
    void push(int x) {
        if(!q1.empty())
        {
            q1.push(x);
        }
        else
        {
            q2.push(x);
        }
    }
    
    int pop() {
        //这一串代码出了一个很严重的错误 我在判断俩个队列谁有数据谁没有数据的时候
        //定义的emptyQ nonEmotyQ的类型是queue<int> 这就成了拷贝数据 
        //但是这样就会出现 pop函数改了数据 q1 q2是不会受影响的
        //那么我在判空的时候 就会出问题
        //应该是定义成指针 而不是拷贝数据  不能用引用 引用一旦定义不能改指向
        // queue<int> emptyQ = q1;//err
        // queue<int> nonEmptyQ = q2; //err
        queue<int>* emptyQ = &q1;
        queue<int>* nonEmptyQ = &q2;
        if(q2.empty())
        {
            emptyQ = &q2;
            nonEmptyQ = &q1;
        }
        while(nonEmptyQ->size() > 1)
        {
            emptyQ->push(nonEmptyQ->front());
            nonEmptyQ->pop();
        }
        //返回栈顶元素
        int top = nonEmptyQ->front();
        nonEmptyQ->pop();
        return top;


        //导数据
        // if(!q1.empty())
        // {
        //     while(q1.size() > 1)
        //     {
        //         q2.push(q1.front());
        //         q1.pop();
        //     }
        //     int top = q1.front();
        //     q1.pop();
        //     return top;
        // }
        // else{
        //     while(q2.size() > 1)
        //     {
        //         q1.push(q2.front());
        //         q2.pop();
        //     }
        //     int top = q2.front();
        //     q2.pop();
        //     return top;
        // }
    }
    
    int top() {
        if(!q1.empty())
        {
            return q1.back();
        }
        else{
            return q2.back();
        }
    }
    
    bool empty() {
        return (q1.empty()) && (q2.empty());
    }
private:
    queue<int> q1;
    queue<int> q2;
};

//用栈实现队列
class MyQueue {
public:
    stack<int> _pushSt;
    stack<int> _popSt;
    MyQueue() { }
    
    void push(int x) {
        _pushSt.push(x);
    }
    
    int pop() {
        //是空就导入数据
        if(_popSt.empty())
        {
            while(!_pushSt.empty())
            {
                _popSt.push(_pushSt.top());
                _pushSt.pop();
            }
        }
        //不是空就直接拿_popst栈顶
        int top = _popSt.top();
        _popSt.pop();
        return top;//返回栈顶元素
    }
    //拿队列front数据
    //跟pop走一样逻辑但是只拿数据不删除数据
    int peek() {
         //是空就导入数据
        if(_popSt.empty())
        {
            while(!_pushSt.empty())
            {
                _popSt.push(_pushSt.top());
                _pushSt.pop();
            }
        }
        //不是空就直接拿_popst栈顶
        return _popSt.top();//返回栈顶元素
    }
    //俩栈都是空那么队列才是空  否则非空
    bool empty() {
        return _pushSt.empty() && _popSt.empty();
    }
};

//设计一个循环队列 C++实现
class MyCircularQueue {
public:

    MyCircularQueue(int k) {
        _a = new int[k + 1];
        _k = k;
        _head =_tail = 0;
    }
    
    bool enQueue(int value) {
        //队列满了
        if(isFull())
            return false;
        //直接插入
        _a[_tail] = value;
        _tail++;

        //插入后要检查边界问题
        if(_tail == _k + 1)
            _tail = 0;
        return true;      
    }
    
    bool deQueue() {
        if(isEmpty())
            return false;
        //head++
        //正常情况下 
        _head++;
        //特殊情况//控制边界
        if(_head == _k + 1)
            _head = 0;
        return true;   
    }
    
    int Front() {
        if(isEmpty())
            return -1;
        return _a[_head];
    }
    
    int Rear() {
        //tail -1 就是尾巴
        if(isEmpty())
            return -1;
        int prev = _tail - 1;
        if(_tail == 0)
            prev = _k;
        return _a[prev];
    }
    
    bool isEmpty() {
        return _tail == _head;
    }
    
    bool isFull() {
        int next = _tail + 1;
        if(next == _k +1)
            next = 0;

        return next == _head;
    }
private:
    //vector<int> _a;
    int* _a;
    int _k;
    int _head;
    int _tail;
};

//链表相关的
//移除链表元素
//思路一 直接在原链表 --遇见删除链接   //头删要单独处理
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
            ListNode* cur = head;
            ListNode* prev = NULL;
            while(cur)
            {
                if(cur->val == val)
                {
                    //头删
                    if(cur == head)
                    {
                        head = cur->next;
                        delete(cur);
                        cur = head;
                    }
                    else
                    {
                         //删除链接
                    ListNode* del = cur;
                    cur = del->next;
                    prev->next = cur;
                    delete(del);
                    }
                   
                }
                else
                {
                    prev = cur;
                    cur = cur->next;        
                }
                
            }
            return head;
    }
};
//方式二
//把不是val的值拿下来尾插到新链表 并删除val的链表
struct ListNode* removeElements(struct ListNode* head, int val) {
    //把不是val的节点拿下来尾插返回新节点
    struct ListNode* cur = head;
    //尾插要找尾 标记尾
    struct ListNode* tail = NULL;
    head = NULL;
    //遍历原链表
    while(cur)
    {
        if(cur->val == val)
        {
            //删除
            //保存删除节点 更新cur 删除删除的节点
            struct ListNode* del = cur;
            cur = del->next;
            free(del);
        }
        else
        {
            //尾插第一次要手动控制
            if(tail == NULL)//没有数据
            {
                tail = cur;
                head = tail;
            }
            else 
            {
                //尾插链接 更新tail
                tail->next = cur;
                tail = tail->next;
            }
            //更新cur
            cur = cur->next;
        }
    }
    if(tail)
    tail->next = NULL;
    return head;
}

//加哨兵位
struct ListNode* removeElements(struct ListNode* head, int val) {
    //把不是val的节点拿下来尾插返回新节点
    struct ListNode* cur = head;
    //尾插要找尾 标记尾
    struct ListNode* tail = NULL;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    tail->next = NULL;
    //遍历原链表
    while(cur)
    {
        if(cur->val == val)
        {
            //删除
            //保存删除节点 更新cur 删除删除的节点
            struct ListNode* del = cur;
            cur = del->next;
            free(del);
        }
        else
        {
                //尾插链接 更新tail
                tail->next = cur;
                tail = tail->next;

            cur = cur->next;
        }
    }
    //哨兵位还是要释放的 我这里没释放
    tail->next = NULL;
    return head->next;
}
//逆置链表
//方式一：拿节点头插
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newHead = NULL;//新链表

    while(cur)
    {
        //头插
        struct ListNode* next = cur->next;
        cur->next = newHead;
        newHead = cur;//
        cur = next;
    }
    return newHead;

}
//方式二 指向颠倒
struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL)
        return NULL;
    struct ListNode* n1, *n2, *n3;
    n1 = NULL;
    n2 = head;
    n3 = n2->next;//如果是空链表 n2就会崩溃
    while(n2)
    {
        //链接
        n2->next = n1;
        //改位置
        n1 = n2;
        n2 = n3;
        if(n3)//不是空才更新n3
        n3 = n3->next;
    }
    return n1;
}


//链表的中间节点
//快慢指针的思路
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow,*fast;
    slow = fast = head;//开始位置
    //要区分奇数偶数的
    while(fast && fast->next)//&&是继续条件 ||是结束条件  
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}


//合并俩个有序链表
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // if(list1 == NULL)
    //     return list2;
    // if(list2 == NULL)
    //     return list1;
    struct ListNode* head, *tail;
    head = tail =(struct ListNode*)malloc(sizeof(struct ListNode));
    tail->next = NULL;
    while(list1 && list2)
    {
        if(list1->val < list2->val)
        {
        
                tail->next = list1;
                tail = tail->next;
            list1 = list1->next;
        }
        else
        {
                tail->next = list2;
                tail = tail->next;
            list2 = list2->next;
        }
    }
    if(list1)
        tail->next = list1;
    if(list2)
        tail->next = list2;
    struct ListNode* list = head->next;
    free(head);
    return list;
}

//链表分割
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        if(pHead == NULL)
            return NULL;
        ListNode* minhead1,*maxhead2,*tail1,*tail2;
        minhead1=tail1=(ListNode*)malloc(sizeof(ListNode));
        tail1->next = NULL;
        maxhead2=tail2=(ListNode*)malloc(sizeof(ListNode));
        tail2->next = NULL;
        //遍历原链表
        while(pHead)
        {
            if(pHead->val < x)
            {
                //比x小的放minhead1
                tail1->next = pHead;
                tail1 = tail1->next;
            }
            else {
                tail2->next = pHead;
                tail2 = tail2->next;
            }
            pHead = pHead->next;
        }
        tail2->next = NULL;
        tail1->next = maxhead2->next;

        return minhead1->next;
    }
};
//链表的回文结构
class PalindromeList {
public:
    ListNode* minddleNode(ListNode* head)
    {
        ListNode* slow, *fast;
        slow = fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* reverseNode(ListNode* head)
    {
        ListNode* n1, *n2,*n3;
        n1 = NULL;
        n2 = head;
        n3 = head->next;
        while(n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if(n3)
            n3 = n3->next;
        }
        return n1;
    }
    bool chkPalindrome(ListNode* A) {
        // write code here
        ListNode* head = A;
        //找中间节点
        ListNode* mid = minddleNode(head);
        //从中间节点开始逆置
        ListNode* rhead = reverseNode(mid);
        //比较俩个链表  

        while( rhead)
        {
            if(head->val != rhead->val)
            {
                return false;
            }
            else {
                head = head->next;
                rhead = rhead->next;
            }
        }
        return true;
    }
};
//相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //尝试用set解决
        //将headA放入set中
        set<ListNode*> l;
        ListNode* cur = headA;
        while(cur != NULL)
        {
            l.insert(cur);
            cur = cur->next;
        }
        //拿headB节点与set中比较看在不在
        cur = headB;
        while(cur != NULL)
        {
            if(l.end() != l.find(cur))
                return cur;
            cur = cur->next;
        }
        return nullptr;
    }
};

//环形链表
class Solution {
public:
    bool hasCycle(ListNode *head) {
      set<ListNode*> node;
      ListNode* cur = head;
      //循环插入set中 检查每次插入是否插入成功  失败就代表有环
      while(cur != NULL)
      {
        auto p = node.insert(cur);
        if(p.second == false)
            return true;
        cur = cur->next;
      }  
      return false;
    }
};

//环形链表2 //找入环点
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //代码不难 
        //简单来说就是 找相遇点 从相遇点跟头一起走 
        ListNode* fast = head, *slow = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
            {
                ListNode* meet = slow;
                while(slow != head)
                {
                    slow = slow->next;
                    head = head->next;
                }
                return head;
            }
        }
        return NULL;
    }
};

//随机链表的复制
struct Node* copyRandomList(struct Node* head) {
	//遍历申请节点  连接在原节点后面
    struct Node* cur = head;
    while(cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        //先不管random 先链接
        copy->next = cur->next;
        cur->next = copy;
        cur = cur->next->next;
    }
    //填充random
    //copy->random = cur->random->next;
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        //可能指向空节点
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    //把copy链表取下来 链接成一个新链表  恢复原链表
    cur = head;
    struct Node* copyhead, *tail;
    copyhead = tail = NULL;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if(tail == NULL)
        {
            copyhead = tail = copy;
        }
        else{
            tail->next = copy;
            tail = tail->next;
        }
        cur->next = next;
        cur = next;
    }
    return copyhead;
}
